package error

import "sort"

type ThroneInheritance struct {
	KingName string                //国王名字
	CurOrder []string              //继承顺序
	Children map[string][]Children //孩子
	Parent   map[string]string     //父亲
}

type Children struct {
	Age  int
	Name string
}

func Constructor(kingName string) ThroneInheritance {
	return ThroneInheritance{
		KingName: kingName,
		CurOrder: make([]string, 0),
		Children: make(map[string][]Children),
		Parent:   make(map[string]string),
	}
}

func (this *ThroneInheritance) Birth(parentName string, childName string) {
	this.Children[parentName] = append(this.Children[parentName], Children{
		Age:  len(this.Children),
		Name: childName,
	})
	this.Parent[childName] = parentName
	if order := this.Successor(childName); order != "" {
		this.CurOrder = append(this.CurOrder, order)
	}
}

func (this *ThroneInheritance) Death(name string) {
	for i, dName := range this.CurOrder {
		if dName == name {
			this.CurOrder = append(this.CurOrder[:i], this.CurOrder[i:]...)
		}
	}
}

func (this *ThroneInheritance) GetInheritanceOrder() []string {
	return this.CurOrder
}

func (this *ThroneInheritance) Successor(x string) string {
	//没有孩子
	if children, ok := this.Children[x]; !ok {
		if this.KingName != x {
			return this.Successor(this.Parent[x])
		} else {
			return ""
		}
	} else {
		notInCurOrder := make([]Children, 0)
		for _, c := range children {
			isExist := false
			for _, order := range this.CurOrder {
				//在继承顺序里
				if c.Name == order {
					isExist = true
					break
				}
			}
			if !isExist {
				notInCurOrder = append(notInCurOrder, c)
			}
		}
		//所有孩子都在继承顺序里
		if len(notInCurOrder) == 0 {
			if this.KingName != x {
				return this.Successor(this.Parent[x])
			} else {
				return ""
			}
		} else {
			sort.Slice(notInCurOrder, func(i, j int) bool {
				return notInCurOrder[i].Age < notInCurOrder[j].Age
			})
			return notInCurOrder[0].Name
		}
	}
}

/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * obj := Constructor(kingName);
 * obj.Birth(parentName,childName);
 * obj.Death(name);
 * param_3 := obj.GetInheritanceOrder();
 */
